package com.my.algorithmlearning.leetcode;

import com.my.algorithmlearning.entity.TreeNode;

/**
 * @ClassName Medium_114_FlattenBinaryTreeToLinkedList
 * @Description https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/solution/zhong-deng-114-er-cha-shu-zhan-kai-wei-l-wlw6/
 * @Author wanghaiwei
 * @Date 2023/4/4 15:36
 */
public class Medium_114_FlattenBinaryTreeToLinkedList {

    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null) {
            return;
        }
        flattenRecursive(root);
    }

    private TreeNode flattenRecursive(TreeNode root) {
        TreeNode leftTreeLastNode;
        if (root.left != null) {
            leftTreeLastNode = flattenRecursive(root.left);
        } else {
            leftTreeLastNode = root;
        }
        TreeNode rightTreeLastNode;
        if (root.right != null) {
            rightTreeLastNode = flattenRecursive(root.right);
        } else {
            rightTreeLastNode = leftTreeLastNode;
        }
        leftTreeLastNode.right = root.right;
        leftTreeLastNode.left = null;
        if (root.left != null) {
            root.right = root.left;
        }
        root.left = null;
        return rightTreeLastNode;
    }

    public static void main(String[] args) {
        Medium_114_FlattenBinaryTreeToLinkedList solution = new Medium_114_FlattenBinaryTreeToLinkedList();
        TreeNode input = new TreeNode(new Integer[]{1, 2, 5, 3, 4, null, 6});
        solution.flatten(input);
        System.out.println("结果1：" + input);

        input = new TreeNode(new Integer[]{0});
        solution.flatten(input);
        System.out.println("结果2：" + input);

        input = new TreeNode(new Integer[]{1, 2, null, 3});
        solution.flatten(input);
        System.out.println("结果3：" + input);
    }
}
